package com.shuzijun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class Combinations{
    public static void main(String[] args) {
         
         Solution solution = new Combinations().new Solution();
        
        
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        private ArrayList<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backTrack(n,k,1,new ArrayList<Integer>());
        return result;

    }

        private void backTrack(int n, int k, int step, ArrayList<Integer> path) {
            if (path.size() == k){
                result.add(new ArrayList<>(path));
                return;
            }
            if (step == n+1){
                return;
            }

            backTrack(n,k,step+1,path);
            path.add(step);
            backTrack(n,k,step+1,path);
            path.remove(path.size()-1);

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}